package com.gxc.integer;

/**
 * 给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。
 *
 * 整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。
 *
 * 返回被除数 dividend 除以除数 divisor 得到的 商 。
 *
 * 注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231,  231 − 1] 。本
 * 题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。
 */
public class Divide {

    public static void main(String[] args) {
        System.out.println(handle(10, 3));
        System.out.println(handle(7, -3));
        System.out.println(handle(-2147483648, -1));
        System.out.println(handle(2147483647, 2));
    }

    public static int handle(int dividend, int divisor) {
        if (dividend==0) return 0;
        int sign = 1;
        if ((dividend<0 && divisor>0) || (dividend>0 && divisor<0)) {
            sign = -1;
        }

        int a = dividend>0?-dividend:dividend;
        int b = divisor>0?-divisor:divisor;
        int res = div(a,b);
        return  sign>0?(res == Integer.MIN_VALUE ?Integer.MAX_VALUE:-res):res;
    }

    /**
     * 用翻倍快速循环
     * // 100/3
     * // 100>3 100>6 100>12 100>24 100>48 100>96 100<192 ---- 使用了 2^5 = 32 个3，还剩 100 - 96 = 4 需要被除
     * // 4>3 4<6                                         ---- 使用了 2^0 = 1  个3，还剩 4   - 3  = 1 需要被除
     * // 1<3
     * @param a
     * @param b
     * @return
     */
    public static int  div(int a, int b)
    {
        if(a > b) return 0;
        int count = -1;
        int tb = b;
        while(tb+tb >= a && tb+tb < 0){ // 溢出之后不再小于0
            tb += tb;
            count += count;
            //System.out.println(tb + " " + count + " " + count*b);
        }
        return count+div(a-tb,b);
    }

    // 100/3
// 100>3 100>6 100>12 100>24 100>48 100>96 100<192 ---- 使用了 2^5 = 32 个3，还剩 100 - 96 = 4 需要被除
// 4>3 4<6                                         ---- 使用了 2^0 = 1  个3，还剩 4   - 3  = 1 需要被除
// 1<3                                             ---- 被除数小于除数，递归结束，总计使用了 33 个 3
    class Solution {
        public int divide(int dividend, int divisor) { // 被除数 除数
            if(divisor == -1 && dividend == Integer.MIN_VALUE) return Integer.MAX_VALUE; // 溢出
            int sign = 1;
            if((dividend > 0 && divisor < 0)||(dividend < 0 && divisor > 0))
                sign = -1;
            // if(divisor == 1) return dividend;
            // if(divisor == -1) return -dividend;
            int a = dividend>0 ? -dividend : dividend;
            int b = divisor>0 ? -divisor : divisor;
            // 都改为负号是因为int 的范围是[2^31, 2^31-1]，如果a是-2^32，转为正数时将会溢出
            //System.out.println(a + " " + b);
            if(a > b) return 0;
            int ans = div(a,b);
            return sign == -1 ? -ans : ans;
        }
        int div(int a, int b)
        {
            if(a > b) return 0;
            int count = 1;
            int tb = b;
            while(tb+tb >= a && tb+tb < 0){ // 溢出之后不再小于0
                tb += tb;
                count += count;
                //System.out.println(tb + " " + count + " " + count*b);
            }
            return count+div(a-tb,b);
        }
    }
}
